1. Field of the Invention
The present invention relates to decoding data in communication or recording systems, and, more particularly, to iterative decoding of block codes.
2. Description of the Related Art
Encoding data with two-dimensional (or higher) block codes and iterative decoding of the encoded data are employed in many systems due to the relatively high coding gain and simple structure of the decoder. Concatenated and product codes may be employed for encoding of data. For these types of codes, two (known as 2-dimensional) or more (N-dimensional) block codes (known as component codes) are combined to create more powerful encoding schemes.
The following definitions may be of use to understand the encoding and decoding methods. A set of binary values U is defined in the Galois field-2 (GF(2)) with elements {+1, xe2x88x921} where +1 is the xe2x80x9cnullxe2x80x9d element under modulo-2 addition. The reliability value, or soft value, L(u) is the log-likelihood ratio of the binary random values in U and is defined as the (natural) log of the ratio of the probability that the random variable U takes on the value u=+1 to the probability that the random variable U takes on the value u=xe2x88x921. The sign of L(u) is used as a hard decision by a detector, and the magnitude of L(u) is used as a reliability statistic (value) for the hard decision. Each binary value u (user data information bit) is encoded to generate coded bits x with soft values L(x). For an (K, N)-systemic code, K bits are equal to the information bits u and (N-K) bits in x contain the parity information.
For example, a product code may employ a one parity-bit check code that, for the 2-dimensional case, encodes two data words having K1 and K2 information bits, respectively (K1 and K2 are integers greater than 0). The product code encoding of the data (i.e., the K1xc2x7K2 information bits) are ordered in a rectangular matrix u as shown in FIG. 1, and the encoding may be a row vector (e.g., K1 information bits) by column vector (e.g., K2 information bits) combination (e.g. GF(2) addition, multiplication, or other linear operation of the binary values) to form the rectangular matrix u. The product code encoding of the data also includes row- and column-wise parity bits pr and pc, respectively. For block codes used as the component codes, for example, encoding K1 and K2 information bits in the horizontal and vertical direction, the encoding may be as follows. Horizontal rows are formed from K2 code words of a (K1, N1) block code Cr having rate R1=(K1/N1) (here, N1 is the total length of a row, and the length of the parity bit information is N1xe2x88x92K1). Vertical columns are formed from K1 code words of a (K2, N2) block code Cc having rate R2=(K2/N2) (here, N2 is the total length of a column, and the length of the parity bit information is N2xe2x88x92K2).
Iterative decoding methods may employ xe2x80x9csoft-in, soft-outxe2x80x9d decoders for decoding data encoded using block codes, such as the product code described above. In an iterative decoding method, a block of encoded data is repetitively decoded by two or more decoding modules until a predetermined number (I) of decoding iterations are complete. In an iterative decoding scheme, the reliability values based on the information are updated at each iteration, utilizing the information extracted from the previous iteration process. Iterative decoding of concatenated and product codes using soft-in, soft-out information is well known in the art and is described in, for example, J. Hagenauer, E. Offer, and L. Papke, Iterative Decoding of Block and Convolutional Codes, I.E.E.E. Transactions on Information Theory, Vol. 42, No. 2, March 1996 whose teachings are incorporated herein.
A soft-in, soft-out decoder decodes soft-input information received as channel values (received sample values Lcxe2x80xa2y) from a transmission medium (the medium may be modeled with constant reliability Lc operating on values y) as well as calculated a priori reliability values Lp(u) for the information bits u. Decoding produces a posteriori reliability values for the output, decoded data. The a priori reliability values Lp(u) may either be 0 for the first iteration (since there is no a priori information) or, after the first iteration, extrinsic reliability values Le(u) for the information bits from a previous iteration. The extrinsic reliability values Le(u) are values based on indirect information contained in the parity bits for an information bit, and may be generated from the a posteriori reliability values.
For each decoding iteration, the decoder completes a decoding operation for each component code of the product code. For the exemplary 2-dimensional product code, decoding of horizontal (row) values uses the input sample values Lcxe2x80xa2y and a priori reliability values Lp(u) to generate output a posteriori row values Lr(u) and the extrinsic row values Lre(u). Next, decoding of vertical (column) values uses the input sample values Lcxe2x80xa2y and the extrinsic row values Lre(u) to generate output a posteriori column values Lc(u) and extrinsic column values Lce(u) before advancing to the next iteration. The extrinsic values Lce(u) may then be used as a priori reliability values Lp(u) for the next iteration. For the last iteration, the output a posteriori values of the last component code decoder are provided as the final decision values Lf(u) corresponding to the decoded sample values.
After each decoding operation (e.g., horizontal or vertical) during each iteration of the decoder, the various defined reliability values (e.g., a posteriori or extrinsic reliability values) must be updated for the next decoding operation (unless the decoding has finished). For an iterative decoder with 2-dimensional parity check product codes having K1xc2x7K2 information bit matrix u, each iteration of the decoder calculates an updated reliability value for the current iteration from the reliability values of the previous operation as follows. The value uij is defined as the (i,j) th value of the (K1xc2x7K2 information bit) matrix u, and the values pir and pjc are defined as the i th row parity bit and the j th column parity bit, respectively. The updated reliability value for uij (L(uij)) for the current iteration of the decoder may be approximated as given in equations (1) and (2):                                                                                           L                  ⁡                                      (                                          u                      ij                                        )                                                  ≈                                                      (                                                                  ∏                                                  k                          ≠                          i                                                                    ⁢                                              xe2x80x83                                            ⁢                                              sign                        ⁡                                                  (                                                                                    L                              xe2x80x2                                                        ⁡                                                          (                                                              u                                kj                                                            )                                                                                )                                                                                      )                                    ⁢                                                            min                                              k                        ≠                        i                                                              ⁢                                          (                                                                        "LeftBracketingBar"                                                                                    L                              xe2x80x2                                                        ⁡                                                          (                                                              u                                kj                                                            )                                                                                "RightBracketingBar"                                                ,                                                  "LeftBracketingBar"                                                                                    L                              xe2x80x2                                                        ⁡                                                          (                                                              p                                i                                r                                                            )                                                                                "RightBracketingBar"                                                                    )                                                                                  ,                                                          1              ≤              i              ≤                              K                1                                                                        (        1        )                                                                                                      L                  ⁡                                      (                                          u                      ij                                        )                                                  ≈                                                      (                                                                  ∏                                                  k                          ≠                          j                                                                    ⁢                                              xe2x80x83                                            ⁢                                              sign                        ⁡                                                  (                                                                                    L                              xe2x80x2                                                        ⁡                                                          (                                                              u                                ik                                                            )                                                                                )                                                                                      )                                    ⁢                                                            min                                              k                        ≠                        j                                                              ⁢                                          (                                                                        "LeftBracketingBar"                                                                                    L                              xe2x80x2                                                        ⁡                                                          (                                                              u                                ik                                                            )                                                                                "RightBracketingBar"                                                ,                                                  "LeftBracketingBar"                                                                                    L                              xe2x80x2                                                        ⁡                                                          (                                                              p                                j                                c                                                            )                                                                                "RightBracketingBar"                                                                    )                                                                                  ,                                                          1              ≤              j              ≤                              K                2                                                                        (        2        )            
where Lxe2x80x2(*) represents the reliability value obtained from the previous iteration. For iterative decoders of the prior art implementing the calculations of equations (1) and (2), a total of K12K2+K1K22 comparators are required to compute the updated reliability value for a K1 by K2 information matrix u.
The present invention relates to generating an updated set of reliability values in an iterative decoder for each dimension of block encoded data. It is an object of the present invention to generate the updated set of reliability values while reducing the number of and complexity of calculations. For an exemplary 2-dimensional product code, an implementation of an iterative decoder employing an exemplary embodiment may use(K1K2+K1K2) comparators rather than (K12K2+K1K22) comparators as required in the prior art.
An embodiment of the present invention searches a current set of reliability values in a dimension of block-encoded data to 1) identify first and second minimum magnitude reliability values and 2) update each sign of the current set of reliability values. For the set of current reliability values, the magnitude of each current reliability value is compared to the first minimum magnitude value and a resulting operation performed based on the comparison. If the current reliability value is greater than the first minimum magnitude value, the magnitude of the updated reliability value corresponding to the current reliability value is set to the first minimum magnitude value; otherwise, the magnitude of the updated reliability value corresponding to the current reliability value is set to the second minimum magnitude value. A sign bit is associated with the magnitude set for each reliability value to provide an updated reliability value.